﻿#define _CRT_SECURE_NO_WARNINGS 1
//day29-01 牛客：排序子序列，题号：100346
//解法：模拟
//const int N = 1e5 + 10;
//int arr[N];
//int n;
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> arr[i];
//    int i = 0;
//    int ret = 0;
//    while (i < n)
//    {
//        if (i == n - 1)
//        {
//            ret++;
//            break;
//        }
//        if (arr[i + 1] > arr[i])
//        {
//            while (i + 1 < n && arr[i + 1] >= arr[i]) i++;
//            ret++;
//        }
//        else if (arr[i + 1] < arr[i])
//        {
//            while (i + 1 < n && arr[i + 1] <= arr[i]) i++;
//            ret++;
//        }
//        else
//        {
//            while (i + 1 < n && arr[i + 1] == arr[i]) i++;
//        }
//        i++;
//    }
//    cout << ret;
//    return 0;
//}


//day29-02 牛客：削减整数，题号：1389171
//解法：贪心
//int main()
//{
//    int T, H;
//    cin >> T;
//    while (T--)
//    {
//        int cut = 1;
//        int ret = 0;
//        cin >> H;
//        while (H)
//        {
//            H -= cut;
//            ret++;
//            if (H % (2 * cut) == 0)
//            {
//                cut = 2 * cut;
//            }
//        }
//        cout << ret << endl;
//    }
//    return 0;
//}


//day29-03 牛客：最⻓上升⼦序列(⼆)，题号：2281421
//解法：贪心+二分查找
//int LIS(vector<int>& a)
//{
//    vector<int> arr;
//    for (int i = 0; i < a.size(); i++)
//    {
//        if (arr.size() == 0 || a[i] > arr.back())
//        {
//            arr.push_back((a[i]));
//            continue;
//        }
//        int left = 0, right = arr.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (arr[mid] >= a[i]) right = mid;
//            else left = mid + 1;
//        }
//        arr[left] = a[i];
//    }
//    return arr.size();
//}